package com.tgy.programmer_code_interview_guide._02_linkedList;

/**
 * @Author: tgy
 * @Date: 1/25/21 11:24 AM
 */
public class _08_把链表划分为小于_等于_大于的部分 {

    public static Node divdeListedList(Node root, int val) {

        if (root == null || root.next == null) {

            return root;
        }

        Node dummyLTNode = new Node(),tailLTNode = dummyLTNode;
        Node dummyEQNode = new Node(),tailEQNode = dummyEQNode;
        Node dummyETNode = new Node(),tailETNode = dummyETNode;

        Node node = root;
        while (node != null) {

            if (node.val < val) {

                tailLTNode.next = node;
                tailLTNode = node;
            }else if (node.val == val) {

                tailEQNode.next = node;
                tailEQNode = node;
            }else {

                tailETNode.next = node;
                tailETNode = node;
            }

            node = node.next;
        }
        // 这里一定要结束链表，不然会保存之前的next
        tailETNode.next = null;

        tailLTNode.next = dummyEQNode.next;
        tailEQNode.next = dummyETNode.next;

        return dummyLTNode.next;
    }

    public static void main(String[] args) {

        Node root = new Node(2);
        root.next = new Node(4);
        root.next.next = new Node(3);
        root.next.next.next = new Node(0);
        root.next.next.next.next = new Node(1);
        root = divdeListedList(root, 3);

        System.out.println(root);
    }
}
